class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
// 创建根节点
const root1 = new TreeNode("A");
// 创建第二层节点
root1.left = new TreeNode("B");
root1.right = new TreeNode("C");
// 创建第三层节点
root1.left.left = new TreeNode("D");
root1.left.right = new TreeNode("E");
root1.right.left = new TreeNode("F");
root1.right.right = new TreeNode("G");
// 创建第四层节点
root1.left.left.left = new TreeNode("H");
root1.left.left.right = new TreeNode("I");
/* 树 1
 *        A
 *      /   \
 *     B     C
 *    /  \   / \
 *   D    E F   G
 *  / \
 * H   I
 */

// 创建根节点
const root2 = new TreeNode("A");
// 创建第二层节点
root2.left = new TreeNode("C");
root2.right = new TreeNode("B");
// 创建第三层节点
root2.left.left = new TreeNode("D");
root2.left.right = new TreeNode("E");
root2.right.left = new TreeNode("F");
root2.right.right = new TreeNode("G");

// 创建第四层节点
root2.left.left.left = new TreeNode("H");
root2.left.left.right = new TreeNode("I");
/* 树 2
 *        A
 *      /   \
 *     B     C
 *    / \   / \
 *   D   E F   G
 *  / \
 * H   I
 */
//左右子树交换不算同一棵树

function compareTree(root1, root2) {
    if(root1===root2) return true
    if(!(root1 && root2)) return false
    if(root1.value !== root2.value) return false
    const leftResult=compareTree(root1.left,root2.left)
    const rightResult=compareTree(root1.right,root2.right)
    return leftResult && rightResult
}






// 创建根节点
const root3 = new TreeNode("A");
// 创建第二层节点
root3.left = new TreeNode("B");
root3.right = new TreeNode("C");
// 创建第三层节点
root3.left.left = new TreeNode("D");
root3.left.right = new TreeNode("E");
root3.right.left = new TreeNode("F");
root3.right.right = new TreeNode("G");
// 创建第四层节点
root3.left.left.left = new TreeNode("H");
root3.left.left.right = new TreeNode("I");
/* 树 3
 *        A
 *      /   \
 *     B     C
 *    /  \   / \
 *   D    E F   G
 *  / \
 * H   I
 */

// 创建根节点
const root4 = new TreeNode("A");
// 创建新的 B 子树
const nodeB = new TreeNode("B");
nodeB.left = new TreeNode("D");
nodeB.right = new TreeNode("E");
nodeB.left.left = new TreeNode("H");
nodeB.left.right = new TreeNode("I");

// 创建新的 C 子树
const nodeC = new TreeNode("C");
nodeC.left = new TreeNode("F");
nodeC.right = new TreeNode("G");
// 交换 B 和 C 子树
root4.left = nodeC;
root4.right = nodeB;

/* 交换 B 和 C 后的树 4
 *        A
 *      /   \
 *     C     B
 *    / \   / \
 *   F   G D   E
 *          / \
 *         H   I
 */
// 8.2 左右子树交换算同一棵树

function compareTree2(tree1, tree2) {
    if(tree1===tree2) return true
    if(!(tree1 && tree2)) return false
    if(tree1.value !== tree2.value) return false
    const result1=compareTree2(tree1.left,tree2.left) && compareTree2(tree1.right,tree2.right)
    const result2=compareTree2(tree1.left,tree2.right) && compareTree2(tree1.right,tree2.left)
    return result1 || result2
}

console.log(compareTree2(root3,root4));
